/*
990. 等式方程的可满足性
https://leetcode.cn/problems/satisfiability-of-equality-equations/
2024/10/12 中等
*/
class Solution {
public:
    int parent[26];
    // 判断给定的一系列等式和不等式是否可能同时成立
    bool equationsPossible(vector<string>& equations) {
        // 初始化每个字母的代表元素为自身
        for (int i = 0; i < 26; ++i) {
            parent[i] = i;
        }
        // 处理等式关系
        for (const string& eq : equations) {
            // 如果当前式子是等式
            if (eq[1] == '=') {
                int find_1 = find(eq[0] - 'a');
                int find_2 = find(eq[3] - 'a');
                // 如果两个字母的代表元素不同，则将它们合并
                if (find_1!= find_2)
                    parent[find_1] = find_2;
            }
        }
        // 处理不等式关系
        for (const string& eq : equations) {
            // 如果当前式子是不等式
            if (eq[1] == '!') {
                int find_1 = find(eq[0] - 'a');
                int find_2 = find(eq[3] - 'a');
                // 如果两个字母的代表元素相同，则返回 false，说明不可能同时满足这些等式和不等式
                if (find_1 == find_2)
                    return false;
            }
        }
        return true;
    }
private:
    // 查找元素的代表元素，并进行路径压缩
    int find(int x) {
        return parent[x] == x? x : parent[x] = find(parent[x]);
    }
};